// 2025/10/26
// 建立四叉树

/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    Node* _construct(vector<vector<int>>& grid, int up, int down, int left, int right)
    {
        if(up == down && left == right)
        {
            return new Node(grid[up][left], true);
        }

        Node* node = new Node;
        int len = (right - left + 1) >> 1;
        node->topLeft = _construct(grid, up, up + len - 1, left, left + len - 1);
        node->topRight = _construct(grid, up, up + len - 1, left + len, right);
        node->bottomLeft = _construct(grid, up + len, down, left, left + len - 1);
        node->bottomRight = _construct(grid, up + len, down, left + len, right);

        if(node->topLeft->isLeaf && node->topRight->isLeaf 
        && node->bottomLeft->isLeaf && node->bottomRight->isLeaf
        && node->topLeft->val == node->topRight->val 
        && node->topRight->val == node->bottomLeft->val
        && node->bottomLeft->val == node->bottomRight->val)
        {
            node->isLeaf = true;
            node->val = node->topLeft->val;
            delete node->topLeft;
            delete node->topRight;
            delete node->bottomLeft;
            delete node->bottomRight;
            node->topLeft = node->topRight = node->bottomLeft = node->bottomRight = nullptr;
        }
        return node;
    }

    Node* construct(vector<vector<int>>& grid) {
        return _construct(grid, 0, grid.size() - 1, 0, grid[0].size() - 1);
    }
};